package com.soul.base.algorithm.level01.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Guava 中的 com.google.common.graph 模块已经提供了图的各种实现
 * <p>
 * 定义
 * 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，
 * G表示一个图，
 * V是图G中顶点的集合，
 * E是图G中边的集合。
 * 图在数据结构中是中多对多的关系，而树则是1对多的关系，树就是一种特别的没有闭环的图。
 * <p>
 * 顶点
 * 图中的顶点就是节点的意思，不过图中任意的节点都算作顶点。
 * 将顶点集合为空的图称为空图。图中任意两个顶点之间都可能存在关系，
 * 顶点之间的逻辑关系用边来表示，边集可以是空的。
 * <p>
 * 无向图
 * 若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(vi,vj)来表示。
 * 如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。
 * <p>
 * 有向图
 * 若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc）。
 * 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。
 * <p>
 * <p>
 * 有向图邻接链表简单实现
 * {@link AdjacencyList#AdjacencyList(E[], E[][])}  构建有向图
 * {@link AdjacencyList#DFS()}  深度优先遍历有向图(Depth First Search)
 * {@link AdjacencyList#BFS()}  广度优先遍历有向图(Breadth-First-Search)
 * {@link AdjacencyList#toString()} ()}  输出有向图
 */
public class AdjacencyList<E> {
    /**
     * 顶点类
     *
     * @param <E>
     */
    private class Node<E> {
        /**
         * 顶点信息
         */
        E data;
        /**
         * 指向第一条依附该顶点的边
         */
        LNode firstEdge;

        public Node(E data, LNode firstEdge) {
            this.data = data;
            this.firstEdge = firstEdge;
        }
    }

    /**
     * 边表节点类
     */
    private class LNode {
        /**
         * 该边所指向的顶点的索引位置
         */
        int vertex;
        /**
         * 指向下一条弧的指针
         */
        LNode nextEdge;
    }

    /**
     * 顶点数组
     */
    private Node<E>[] vertexs;

    /**
     * 创建图
     *
     * @param vexs  顶点数组
     * @param edges 边二维数组
     */
    public AdjacencyList(E[] vexs, E[][] edges) {
        /*初始化顶点数组,并添加顶点*/
        vertexs = new Node[vexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            vertexs[i] = new Node<>(vexs[i], null);
        }
        /*初始化边表,并添加边节点到边表尾部,即采用尾插法*/
        for (E[] edge : edges) {
            // 读取一条边的起始顶点和结束顶点索引值
            int p1 = getPosition(edge[0]);
            int p2 = getPosition(edge[1]);
            // 初始化lnode1边节点 即表示p1指向p2的边
            LNode lnode1 = new LNode();
            lnode1.vertex = p2;
            // 将LNode链接到"p1所在链表的末尾"
            if (vertexs[p1].firstEdge == null) {
                vertexs[p1].firstEdge = lnode1;
            } else {
                linkLast(vertexs[p1].firstEdge, lnode1);
            }
        }
    }

    /**
     * 获取某条边的某个顶点所在顶点数组的索引位置
     *
     * @param e 顶点的值
     * @return 所在顶点数组的索引位置, 或者-1 - 表示不存在
     */
    private int getPosition(E e) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i].data == e) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 将lnode节点链接到边表的最后,采用尾插法
     *
     * @param first 边表头结点
     * @param node  将要添加的节点
     */
    private void linkLast(LNode first, LNode node) {
        while (true) {
            if (first.vertex == node.vertex) {
                return;
            }
            if (first.nextEdge == null) {
                break;
            }
            first = first.nextEdge;
        }
        first.nextEdge = node;
    }

    /**
     * 深度优先搜索遍历图的递归实现,类似于树的先序遍历
     * 因此模仿树的先序遍历,同样借用栈结构,这里使用的是方法的递归,隐式的借用栈
     *
     * @param i       顶点索引
     * @param visited 访问标志数组
     */
    private void DFS(int i, boolean[] visited) {
        //索引索引标记为true ,表示已经访问了
        visited[i] = true;
        System.out.print(vertexs[i].data + " ");
        //获取该顶点的边表头结点
        LNode node = vertexs[i].firstEdge;
        //循环遍历该顶点的邻接点,采用同样的方式递归搜索
        while (node != null) {
            if (!visited[node.vertex]) {
                DFS(node.vertex, visited);
            }
            node = node.nextEdge;
        }
    }

    /**
     * 深度优先搜索遍历图,类似于树的前序遍历,
     */
    public void DFS() {
        //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有顶点都没有被访问
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        /*循环搜索*/
        for (int i = 0; i < vertexs.length; i++) {
            //如果对应索引的顶点的访问标记为false,则搜索该顶点
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        /*走到这一步,说明顶点访问标记数组全部为true,说明全部都访问到了,深度搜索结束*/
        System.out.println();
    }


    /**
     * 广度优先搜索图,类似于树的层序遍历
     * 因此模仿树的层序遍历,同样借用队列结构
     */
    public void BFS() {
        // 辅组队列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有顶点都没有被访问
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            //如果访问方剂为false,则设置为true,表示已经访问,然后开始访问
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i].data + " ");
                indexLinkedList.add(i);
            }
            //判断队列是否有值,有就开始遍历
            if (!indexLinkedList.isEmpty()) {
                //出队列
                Integer j = indexLinkedList.poll();
                LNode node = vertexs[j].firstEdge;
                while (node != null) {
                    int k = node.vertex;
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.print(vertexs[k].data + " ");
                        //继续入队列
                        indexLinkedList.add(k);
                    }
                    node = node.nextEdge;
                }
            }
        }
        System.out.println("\n");
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < vertexs.length; i++) {
            stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
            LNode node = vertexs[i].firstEdge;
            while (node != null) {
                stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append(")");
                node = node.nextEdge;
                if (node != null) {
                    stringBuilder.append("->");
                } else {
                    break;
                }
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        //顶点数组 添加的先后顺序对于遍历结果有影响
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //边二维数组 {'a', 'b'}表示顶点a->b的边  添加的先后顺序对于遍历结果有影响
        Character[][] edges = {
                {'A', 'C'},
                {'A', 'D'},
                //对于有向图来说是多余的边关系,在linkLast方法中做了判断,并不会重复添加
                {'A', 'D'},
                //对于有向图来说不是多余的边关系
                {'D', 'A'},

                {'A', 'F'},
                {'B', 'C'},
                {'C', 'D'},
                {'E', 'G'},
                {'E', 'B'},
                {'D', 'B'},
                {'F', 'G'}};
        // 构建图有向图
        AdjacencyList<Character> adjacencyList = new AdjacencyList<>(vexs, edges);
        //输出图
        System.out.println(adjacencyList);
        //深度优先遍历
        adjacencyList.DFS();
        //广度优先遍历
        adjacencyList.BFS();
    }
}

